//MIT License

//Copyright (c) 2017 腾讯云

//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:

//The above copyright notice and this permission notice shall be included in all
//copies or substantial portions of the Software.

//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
//SOFTWARE.

#ifndef MPLRUCACHE_H
#define MPLRUCACHE_H

#include <iostream>
#include <list>
#include <mutex>
#include <stdexcept>
#include <unordered_map>
#include <functional>

namespace MP{

/**
 * 适用于缓存内容为存数字等值类型数据
 */
template <typename KeyType, typename ValueType>
class LruCache {
public:
    using KeyValuePair = std::pair<KeyType, ValueType>;
    using ListIterator = typename std::list<KeyValuePair>::iterator;

    //初始化时必须明确LruCache中容器的最大元素个数
    LruCache(size_t size) : m_max_size(size) {}

    ~LruCache() {}

    /**
     * @brief 插入缓存元素
     * @param key
     * @param value
     */
    void Put(const KeyType& key, const ValueType& value) {
        std::lock_guard<std::mutex> lock(m_mutex);

        m_entry_list.emplace_front(key, value);
        auto it = m_entry_map.find(key);
        if (it != m_entry_map.end()) {
            m_entry_list.erase(it->second);
        } else {
            if (m_entry_list.size() > m_max_size) {
                m_entry_map.erase(m_entry_list.back().first);
                m_entry_list.pop_back();
            }
        }

        m_entry_map[key] = m_entry_list.begin();
    }

    const ValueType& Get(const KeyType& key) {
        std::lock_guard<std::mutex> lock(m_mutex);

        auto it = m_entry_map.find(key);
        if (it == m_entry_map.end()) {
            throw std::range_error("No such key in cache");
        } else {
            m_entry_list.emplace_front(key, it->second->second);
            m_entry_list.erase(it->second);
            m_entry_map[key] = m_entry_list.begin();
            return m_entry_list.begin()->second;
        }
    }

    bool Exist(const KeyType& key) const {
        std::lock_guard<std::mutex> lock(m_mutex);

        return m_entry_map.find(key) != m_entry_map.end();
    }

    size_t Size() const {
        std::lock_guard<std::mutex> lock(m_mutex);

        return m_entry_map.size();
    }

private:
    //双向链表
    std::list<KeyValuePair> m_entry_list;
    //基于hash表实现的键值对
    std::unordered_map<KeyType, ListIterator> m_entry_map;
    //缓存的最大元素个数
    size_t m_max_size;
    //互斥量
    mutable std::mutex m_mutex;
};


/**
 * 适用于缓存内容为指针(需要C++11支持)
 */
template <typename KeyType, typename ObjType>
class LruObjCache {
public:
    using REMOVE_FUNC_CALLBACK = std::function<void(KeyType, ObjType*)>;

    LruObjCache(size_t capacity, const REMOVE_FUNC_CALLBACK& func)
        : capacity_(capacity)
        , remove_func_(func) { }

    ~LruObjCache() {
        for (auto i : values_) {
            auto key = i.first;
            auto obj = i.second.first;
            remove_func_(key, obj);
        }
    }

    ObjType* get(KeyType key) {
        auto it = values_.find(key);
        if (it == values_.end())
            return nullptr;
        auto& it_in_list = it->second.second;
        latest_use_.erase(it_in_list);
        it_in_list = latest_use_.insert(latest_use_.end(), key);
        return it->second.first;
    }

    void put(KeyType key, ObjType* obj) {
        auto it = values_.find(key);
        if (it == values_.end()) {
            //没在里面
            if (latest_use_.size() >= capacity_) {
                auto& v = latest_use_.front();
                auto i = values_.find(v);
                if (i != values_.end()) {
                    remove_func_(v, i->second.first);
                    i = values_.erase(i);
                }

                latest_use_.pop_front();
            }

            auto it_in_list = latest_use_.insert(latest_use_.end(), key);
            values_[key] = std::make_pair(obj, it_in_list);
        } else {
            it->second.first = obj;
            auto& it_in_list = it->second.second;
            latest_use_.erase(it_in_list);
            it_in_list = latest_use_.insert(latest_use_.end(), key);
        }
    }

private:
    std::unordered_map<KeyType, std::pair<ObjType*, typename std::list<KeyType>::iterator>> values_;
    std::list<KeyType> latest_use_;
    size_t capacity_;
    REMOVE_FUNC_CALLBACK remove_func_ = nullptr;
};



}   //END MP


#endif // MPLRUCACHE_H
